package main

import "math"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var ans = math.MinInt32

func maxPathSum(root *TreeNode) int {
	ans = math.MinInt32
	foo(root)
	return ans
}

func max(a int, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func foo(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left := max(0, foo(root.Left))
	right := max(0, foo(root.Right))
	val := root.Val + left + right
	if ans < val {
		ans = val
	}
	return max(left, right) + root.Val
}

func main() {

}
